Unless specifically indicated herein, the approaches described in this section should not be construed as prior art to the claims of the present application and are not admitted to be prior art by inclusion in this section.
Byzantine fault tolerant (BFT) protocols are commonly used in distributed systems that provide replicated services (i.e., services whose operations and state are mirrored on each system node, referred to as a “replica”) to provide resilience against arbitrary failures that prevent replicas from reaching consensus on matters critical to their correct operation. For example, in a distributed system that comprises N total replicas, the system will typically employ a BFT protocol to ensure that when replicas 1 . . . N receive client requests to perform service operations, the non-faulty replicas will sequence execution of the service operations in an identical manner. Generally speaking, N must be greater than or equal to 3f+1 (where f is the maximum number of faulty replicas) in order for the BFT protocol to guarantee that all non-faulty replicas agree on the same sequence number for each service operation (referred to as “safety”), and that every service operation will eventually be assigned a sequence number given the synchrony assumptions of the protocol (referred to as “liveness”).
In some distributed systems that use BFT, there is a need for at least a portion of the state handled/maintained by each replica to be hidden (i.e., kept secret) from that individual replica and any group of f replicas, but capable of being revealed (i.e., reconstructed) by f+1 replicas in response to an explicit request. For instance, if the replicated service provided by a distributed system is a data storage service, the client or some other entity may want a portion of each data entry persisted via the data storage service to be private. By keeping this private data secret from any group of f replicas, an adversary that takes over those replicas cannot learn the content of the data. At the same time, by enabling a quorum of f+1 replicas to reconstruct the secret, the system as a whole can remain in control of its data and thus can implement features that rely on such control.
There is a class of cryptographic algorithms known as verifiable secret sharing (VSS) that can be applied to BFT to meet the secrecy and reconstruction requirements mentioned above. VSS generally involves dividing, by a dealer, a secret value s into N shares and distributing the shares to N shareholders in such a way that at least a threshold t shares from shareholders are required to reconstruct s. Thus, VSS can enable secret sharing in the context of BFT by having the BFT client act as the VSS dealer, having the BFT replicas act as the VSS shareholders, and setting threshold t to f+1. VSS also exhibits the property of “completion”, which guarantees that at least t non-faulty shareholders will have a valid share at the end of the sharing phase so that a consistent secret value s* can be reconstructed.
One complication with incorporating VSS into a BFT protocol is that the completion property is not sufficient for ensuring liveness of the BFT protocol. In BFT, each replica is required to authenticate a client request, which a non-faulty replica cannot do until it receives a valid share of secret s. Thus, the standard completion property implies that up to f non-faulty replicas may not be able to authenticate the request and participate in the BFT protocol. This in turn means that an adversary in control of f faulty replicas can simply refuse to participate in the sequencing of the request and thereby break the liveness of the protocol.
There are certain VSS schemes that provide a stronger version of the completion property, known as “strong completion,” which guarantees that the reconstruction of s will succeed with any N−f shareholders. This strong completion property overcomes the deficiency of standard completion described above and ensures liveness when VSS is used in conjunction with BFT. However, a significant drawback of existing VSS schemes that provide strong completion is that they incur, on the part of the dealer, quadratic communication and cryptographic computation overhead during the sharing phase with respect to the number of shareholders. In contrast, the communication and cryptographic computation overhead of the client in BFT protocols is linear with respect to the number of replicas. This means that incorporating an existing strong completion VSS scheme into BFT increases the client overhead by a non-constant amount, which can make this combination impractical for use in large-scale distributed systems.